1120. Maximum Average Subtree
Medium

Given the root of a binary tree, find the maximum average value of any subtree of that tree.

(A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.)

 

Example 1:

Input: [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

 

Note:

  1. The number of nodes in the tree is between 1 and 5000.
  2. Each node will have a value between 0 and 100000.
  3. Answers will be accepted as correct if they are within 10^-5 of the correct answer.
Accepted
33,620
Submissions
52,255
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
Can you find the sum of values and the number of nodes for every sub-tree ?
Show Hint 2
Can you find the sum of values and the number of nodes for a sub-tree given the sum of values and the number of nodes of it's left and right sub-trees ?
Show Hint 3
Use depth first search to recursively find the solution for the children of a node then use their solutions to compute the current node's solution.

Average Rating: 4.67 (12 votes)

Premium

Solution


Approach 1: Postorder Traversal

Intuition and Algorithm

To calculate average value of a subtree rooted at node, we need two things:

  1. Sum of all values of the nodes in the subtree of node, let's refer to it as ValueSum(node).
  2. Count of the nodes in the node subtree, let's refer to it as NodeCount(node).

Then, the average for subtree rooted at node will be ValueSum(node)/NodeCount(node).

Now, to calculate these values for a subtree rooted at node, we can derive them from the child nodes of node.

  1. ValueSum(node) = ValueSum(node.left) + ValueSum(node.right) + Value(node)
  2. NodeCount(node) = NodeCount(node.left) + NodeCount(node.right) + 1

Also, for any leaf node leaf, we know that:

  1. ValueSum(leaf) = node.val
  2. NodeCount(leaf) = 1

Looking at these equations, we can see that we can calculate average for each of the node in the tree by traversing bottom up i.e. first visit and calculate ValueSum and NodeCount for child nodes and then use these child nodes values to solve for parent node. This order of tree traversal is popularly known as postorder traversal.

img

You can read more about different binary tree traversals here.

Complexity Analysis

  • Time complexity : O(N)O(N), where NN is the number of nodes in the tree. This is because we visit each and every node only once, as we do in postorder traversal.

  • Space complexity : O(N)O(N), because we will create NN states for each of the nodes in the tree. Also, in cases where we have a skewed tree, we will implicitly maintain a recursion stack of size NN, hence space complexity from this will also be O(N)O(N).

Report Article Issue

Comments: 8
ssb_usa's avatar
Read More

Simple DFS solution and understandable code -
Time complexity : O(n)
Space complexity: O(n)

class Solution:
    def maximumAverageSubtree(self, root: TreeNode) -> float:
        if not root:
            return 0
        
        def dfs(node=root):
            
            # if node is None, return 0 as sum and 0 as no. of nodes
            if node is None:
                return (0, 0)
            
            # go to left subtree and get total sum on that subtree, and the total nodes
            sum_left, node_cnt_left = dfs(node.left)
            
            # go to right subtree and get total sum on that subtree, and the total nodes
            sum_right, node_cnt_right = dfs(node.right)
            
            # calculate the total sum
            _total_sum = node.val + sum_left + sum_right
            # calculate the total no. of nodes
            _total_nodes = 1 + node_cnt_left + node_cnt_right
            # compute the avg
            _avg = _total_sum / _total_nodes
            
            # update max_avg if it is smaller than computed avg
            if _avg > self.max_avg:
                self.max_avg = _avg
            
            # return the total sum and total nodes to previous stack call.
            return (_total_sum, _total_nodes)
        
        # set a variable to track max_avg
        self.max_avg = float("-inf")
        dfs()

        return self.max_avg

16
Reply
Share
Report
Legitao's avatar
Read More

Should the space complexity be O(logN) on average, O(N) for the worst case?
I think we only need to think of the stack frame.
The space for states is O(1) since it is not kept in memory all time. As soon as the current level of recursion returns, the state from subtrees is deleted in memory.

5
Show 2 replies
Reply
Share
Report
kahack's avatar
Read More

// we can keep the max average at class level

class Solution {
    
    class State {
        int sum;
        int nodeCount;
        
        public State(int sum, int nodeCount) {
            this.sum = sum;
            this.nodeCount = nodeCount;
        }
    }
    
    double max = Double.MIN_VALUE;
    
    public double maximumAverageSubtree(TreeNode root) {
        maxAverage(root);
        return max;
    }
    
    private State maxAverage(TreeNode root) {
        if (root == null) return new State(0,0);
        
        State left = maxAverage(root.left);
        State right = maxAverage(root.right);
        
        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.sum + right.sum + root.val;
        double average = (1.0 * (sum)) / nodeCount;
        
        max = Math.max(max, average);
        
        return new State(sum, nodeCount);
    }
}

0
Reply
Share
Report
cerberuz's avatar
Read More

Space used by State is O(1), not O(N).
Once you return to current node after recursion, you can free up the memory used by state OR in java it is not being referenced anywhere else except by the reference in current method scope, so will be eligible for Garbage Collection.

0
Show 10 replies
Reply
Share
Report
nagakiran1's avatar
Read More

in test case 25, [4,3,1,0,2] max ave of 4 is 2.66, how come expects it 2
would someone comment please.

def maximumAverageSubtree(self, root: TreeNode) -> float:
    
    def dfs(node, ma):
        if node is None:
            return

        te = [node.val]
        if node.left:
            te.append(node.left.val)
        if node.right:
            te.append(node.right.val)
        self.ma = max(self.ma, sum(te)/len(te))

        dfs(node.left, ma)
        dfs(node.right, ma)
        return 
    self.ma = 0
    dfs(root, 0)
    print(self.ma)
    return self.ma

0
Reply
Share
Report
ambitechstrous's avatar
Read More

Python solution, as this one only has Java/C++ using classes and structs.

class Solution:
def maximumAverageSubtree(self, root: TreeNode) -> float:

    max_avg = 0
    
    def getMaxAvgValue(root: TreeNode) -> (float, int):
        nonlocal max_avg
        if root == None:
            return 0,0
        
        total_left, nodes_left = getMaxAvgValue(root.left)
        total_right, nodes_right = getMaxAvgValue(root.right)
        
        total_curr = root.val + total_left + total_right 
        nodes_curr = (nodes_left + nodes_right + 1)
        avg = total_curr / nodes_curr
        if avg > max_avg:
            max_avg = avg
            
        return total_curr, nodes_curr
    
    getMaxAvgValue(root)
    return max_avg

Runs faster than 96% at O(N) time. You could also do same as Java Impl and return the elements as class above, or make it return thruple instead of tuple with max_avg in thruple.

0
Reply
Share
Report
tupac_shakur's avatar
Read More

A simple dfs

 fun maximumAverageSubtree(root: TreeNode?): Double {
        var ans = 0.0    
        if (root == null) {
            return ans
        }      
        fun dfs(node: TreeNode?): Pair<Int, Int> { // returns <sum, number of nodes>
            if (node == null) {
                return 0 to 0
            }
            if (node.left == null && node.right == null) {
                return node.`val` to 1
            }
            val (lSum, lNodes) = dfs(node.left)
            val (rSum, rNodes) = dfs(node.right)
            val curSum = lSum + rSum + node.`val`
            val curNodes = lNodes + rNodes + 1
            if (lNodes != 0) { // if check for dividebyzero exception
                ans = maxOf(ans, lSum / (lNodes * 1.0))
            }
            if (rNodes != 0) {
                ans = maxOf(ans, rSum / (rNodes * 1.0))
            }
            if (curNodes != 0) {
                ans = maxOf(ans, curSum / (curNodes * 1.0))
            }
            return curSum to curNodes
        }     
        dfs(root)
        return ans
    }

0
Reply
Share
Report
jingleleung's avatar
Read More

This one should really be an easy. DFS is the first thing everyone tries when doing binary trees and the algo is literally just DFS and add up the numbers.

-8
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.